This invention relates to network routers and more particularly, to methods for compressing routing tables used by the routers to route network messages.
Routers are specialized computing devices that route digital messages over a network. Routers receive messages from one location (e.g., source computer or another router) and forward them to the next destination (e.g., destination computer or another router) over the most efficient available path.
Routers use routing tables to direct message traffic over a network. Routing tables have multiple entries (e.g., thousands to tens of thousands), with each entry being an address of a destination device. For instance, in the Internet context, each entry consists of the 32-bit IP (Internet Protocol) address such as xe2x80x9c192.56.7.48xe2x80x9d. The IP address may also include a prefix length, such as 8, 16, or 24. The prefix lengths specify how many bits a router should consider for a next route. For instance, if the IP address xe2x80x9c192.56.7.48xe2x80x9d is assigned a prefix length of xe2x80x9c16xe2x80x9d, the router need only consider the first two bytes to determine a next route and may effectively read the IP address as xe2x80x9c192.56.0.0xe2x80x9d.
Associated with each entry in the routing table is a xe2x80x9cnext hopxe2x80x9d value that indexes into a second table. The second or xe2x80x9cnext hopxe2x80x9d table has fewer entries (e.g., 10-100 entries) to identify IP addresses of a next router or destination port in the network. For instance, the IP address xe2x80x9c192.56.7.48/16xe2x80x9d may have an associated next hop value of xe2x80x9c17xe2x80x9d, meaning that the IP address for the next router is at location 17 in the next hop table.
The router uses the routing table and next hop table to route messages most efficiently through the network. When a packet arrives at a router, the router first finds the address in the routing table that provides the closest match to the destination address. The general rule is that the IP address with the longest-matching prefix in comparison to the destination address is selected. The router then locates the next hop associated with the selected IP address and routes the packet to the next router referenced by the IP address in the next hop table indexed by the next hop. There are many different high-speed algorithms to quickly look up addresses in the routing and next hop tables.
Due to the explosive growth of content being made available on the World Wide Web, the Internet is rapidly growing to fill every corner of the world. The demands of the Internet backbone routers are commensurately increasing. Nodes are being added to the network at an extremely fast rate. It is estimated that the number of routes in the Internet backbone has been growing by 10,000 routes per year. More sophisticated and faster routers are being developed, with larger routing tables, to accommodate the increasing number of routes. To improve the speed and reliability of routers, it is desirable to reduce the size of the routing table in ways that do not harm the functionality or efficiency of the router.
Toward this end, this invention is directed to techniques for reducing the size of the routing table.
This invention concerns routers and methods for compressing router tables employed in routers. The methods produce smaller, yet functionally equivalent tables.
In one implementation, a method for compressing a routing table involves constructing a binary tree representation of the routing table. The binary tree has multiple nodes, wherein parent nodes at one level branch to zero, one, or two child nodes at a next lower level. The compression method makes three passes through the tree. In a first pass, the compression method propagates routing information down to the leaf nodes of the tree (i.e., nodes that do not branch to lower children nodes). During this pass, the program assigns every leaf node in the tree an associated next hop or an inherited next hop from a higher level ancestral node.
In a second pass, the compression method migrates the more prevalent next hops up the tree. This bottom up pass involves forming a set of next hops at a parent node by supernetting the sets of next hops A and B for a pair of child nodes corresponding to the parent node, according to the following operation:
A*B=A∪B, if A∩B=xcfx86
A∩B, if A∩Bxe2x89xa0xcfx86
where xe2x80x9cA*Bxe2x80x9d is the set of next hops formed at the parent node.
In the third pass, the compression method eliminates redundant branches in the tree. This top down pass begins at the root node, and subsequently each parent node, and selects a next hop from a parent node. The method then examines a child node branching from the parent node to determine whether the selected next hop is an element of next hops for the child node. If it is, the method eliminates the next hops for the child node.
After the three-pass process restructures the tree, the compression method converts the free back to a new routing table.